import java.util.*;

//自底向上的层序遍历
class Solution2{
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while (!qu.isEmpty()) {
            List<Integer> list1 = new ArrayList<>();
            int size = qu.size();
            while (size > 0) {
                TreeNode cur = qu.poll();
                size--;
                list1.add(cur.val);
                if (cur.left != null) {
                    qu.offer(cur.left);
                }
                if (cur.right != null) {
                    qu.offer(cur.right);
                }
            }
            list.add(0, list1);//一直进行头插
        }
        return list;
    }
    }